/*
 * @lc app=leetcode.cn id=502 lang=cpp
 * @lcpr version=30204
 *
 * [502] IPO
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        // 将项目按所需资本从小到大排序
        vector<pair<int, int>> projects;
        int n = profits.size();
        for (int i = 0; i < n; ++i) {
            projects.emplace_back(capital[i], profits[i]);
        }
        sort(projects.begin(), projects.end());
        
        // 最大堆用于存储当前可投资项目的利润
        priority_queue<int> maxHeap;
        int idx = 0; // 记录已处理的项目索引
        
        for (int i = 0; i < k; ++i) {
            // 将所有当前资本可承担的项目加入堆
            while (idx < n && projects[idx].first <= w) {
                maxHeap.push(projects[idx].second);
                ++idx;
            }
            
            // 若没有可投资的项目，提前结束
            if (maxHeap.empty()) {
                break;
            }
            
            // 选择利润最大的项目投资
            w += maxHeap.top();
            maxHeap.pop();
        }
        
        return w;
    }
};
// @lc code=end



/*
// @lcpr case=start
// 2\n0\n[1,2,3]\n[0,1,1]\n
// @lcpr case=end

// @lcpr case=start
// 3\n0\n[1,2,3]\n[0,1,2]\n
// @lcpr case=end

 */

